package 抽象数据类型;

public class BSTBinTreeNode extends BinTreeNode {
    public BSTBinTreeNode(Node e) {
        super(e);
    }

    public static BinTreeNode search(BinTreeNode root, BinTreeNode ele) {
        return binTSearchRe(root, ele);
    }

    private static BinTreeNode binTSearchRe(BinTreeNode root, Object ele) {
        if (root == null) {
            return null;
        }
        switch (root.compareTo((BinTreeNode) ele)) {
            case 0:
                return root;

            case 1:
                return binTSearchRe(root.getRChild(), ele);

            default:
                return binTSearchRe(root.getLChild(), ele);

        }
    }

    private BSTBinTreeNode binTSearchReTwo(BSTBinTreeNode root, Object ele) {

        while (root != null) {
            switch (root.compareTo((BSTBinTreeNode) ele)) {
                case 0:
                    return root;

                case 1:
                    root = (BSTBinTreeNode) root.getRChild();

                default:
                    root = (BSTBinTreeNode) root.getLChild();

            }
        }
        return null;
    }

    private static BinTreeNode min(BinTreeNode root) {
        while (root != null && root.hasLChild()) {
            root = root.getLChild();
        }
        return root;
    }

    private static BinTreeNode max(BinTreeNode root) {
        while (root != null && root.hasRChild()) {
            root = root.getRChild();
        }
        return root;
    }

    private Node getSuccessor(BinTreeNode root) {
        if (root == null) {
            return null;
        }
        if (root.hasRChild()) {
            return min(root.getRChild());
        }
        while (root.isRChild()) {
            root = root.getParent();
        }
        return root.getParent();
    }

    private static BinTreeNode getPreDecessor(BinTreeNode root) {
        if (root == null) {
            return null;
        }
        if (root.hasLChild()) {
            return max(root.getRChild());
        }
        while (root.isLChild()) {
            root = root.getParent();
        }
        return root.getParent();
    }

    public static BinTreeNode insert(BinTreeNode root, Node ele) {
        if (root == null) {
            root = new BSTBinTreeNode(ele);
            return root;
        }
        BinTreeNode currentNode = root;
        BinTreeNode node = new BinTreeNode(ele);
        while (currentNode != null) {
            switch (currentNode.compareTo(node)) {
                case 1:
                    if (currentNode.hasRChild()) {
                        currentNode = currentNode.getRChild();
                    } else {
                        currentNode.setRChild(node);
                        return root;
                    }
                    break;
                case -1:
                    if (currentNode.hasLChild()) {
                        currentNode = currentNode.getLChild();
                    } else {
                        currentNode.setLChild(node);
                        return root;
                    }
                    break;
                default:
                    BinTreeNode tempNode = currentNode.getLChild();
                    currentNode.setLChild(node);
                    node.setLChild(tempNode);
                    return root;

            }
        }
        return root;

    }

    public static BinTreeNode remove(BinTreeNode root, Comparable ele) {
        BinTreeNode node = new BinTreeNode(new Node(ele));
        BinTreeNode specifyNode = search(root, node);
        BinTreeNode temp = null;
        if (specifyNode == null) {
            return null;
        }
        if (specifyNode.hasLChild() && specifyNode.hasRChild()) {
            temp = max(specifyNode.getLChild());
            specifyNode.setData(temp.getData());
            specifyNode.setLChild(remove(specifyNode.getLChild(), temp.getData()));
        } else {
            if (specifyNode.hasLChild()) {
                if (specifyNode.isLChild()) {
                    specifyNode.getParent().setLChild(specifyNode.getLChild());
                } else if (specifyNode.isRChild()) {

                    specifyNode.getParent().setRChild(specifyNode.getLChild());
                }
            } else if (specifyNode.hasRChild()) {

                if (specifyNode.isLChild()) {
                    specifyNode.getParent().setLChild(specifyNode.getRChild());
                } else if (specifyNode.isRChild()) {
                    specifyNode.getParent().setRChild(specifyNode.getRChild());
                }
            } else {
                if (specifyNode.isLChild()) {
                    specifyNode.getParent().setLChild(null);
                } else {
                    specifyNode.getParent().setRChild(null);
                }


            }
        }
        return root;
    }

    public static boolean isBST(BinTreeNode binTreeNode) {
        if (binTreeNode == null) {
            return true;
        }
        if (((binTreeNode.hasLChild() && binTreeNode.getLChild().compareTo(binTreeNode) <= 0)
        ) ||
                ((binTreeNode.hasRChild() && binTreeNode.getRChild().compareTo(binTreeNode) >= 0)
                )) {
            return false;

        }
        if ((binTreeNode.hasLChild() && binTreeNode.compareTo(max(binTreeNode.getLChild())) >= 0 ||
                (binTreeNode.hasRChild() && binTreeNode.compareTo(min(binTreeNode.getRChild())) <= 0))) {
            return false;
        }
        return isBST(binTreeNode.getLChild()) && isBST(binTreeNode.getRChild());

    }

    public static BSTBinTreeNode buildBST(String[] arr, int left, int right) {
        BSTBinTreeNode insertNode;
        if (left > right) {
            return null;
        } else {
            int mid = (left + right) / 2;
            insertNode = new BSTBinTreeNode(new Node(arr[mid]));
            insertNode.setLChild(buildBST(arr, left, mid - 1));
            insertNode.setRChild(buildBST(arr, mid + 1, right));
        }
        return insertNode;

    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 4, 6, 7, 9, 10};
        String[] arrs = new String[arr.length];
        for (int i = 0; i < arr.length; i++) {
            arrs[i] = arr[i] + "";

        }
        BSTBinTreeNode node = buildBST(arrs, 0, arr.length - 1);
        levelOrder(node);

    }

    /*public static void main(String[] args) {
        Object[] eles = {15, 6, 18, 3, 2, 4, 7, 13, 9, 17, 20};
        BinTreeNode root = null;

        for (Object ele : eles) {
            root = insert(root, ele);
        }
        remove(root, 2);
        levelOrder(root);
        remove(root, 3);
        levelOrder(root);
        remove(root, 7);
        levelOrder(root);
        remove(root, new Integer(15));
        levelOrder(root);

        BinTreeNode binTreeNode = new BinTreeNode();
        binTreeNode.setData(1);

        binTreeNode.setRChild(new BinTreeNode(2));
        binTreeNode.setLChild(new BinTreeNode(-5));
        binTreeNode.getRChild().setRChild(new BinTreeNode(4));
        binTreeNode.getLChild().setRChild(new BinTreeNode(-3));
        System.out.println(isBST(binTreeNode));

    }*/

}
